Field of the Invention
Embodiments of the present invention relate, in general, to estimation of an object's position and more particularly to mobile localization using sparse using time-of-flight ranges and dead reckoning.
Relevant Background
Service providers of all types have begun to recognize that positioning services (i.e., services that identify the position of an object, wireless terminal or the like) may be used in various applications to provide value-added features. A service provider may also use positioning services to provide position-sensitive information such as driving directions, local information on traffic, gas stations, restaurants, hotels, and so on. Other applications that may be provided using positioning services include asset tracking services, asset monitoring and recovery services, fleet and resource management, personal-positioning services, autonomous vehicle guidance, conflict avoidance, and so on. These various applications typically require the position of each affected device be monitored by a system or that the device be able to continually update its position and modify its behavior based on its understanding of its position.
Various systems may be used to determine the position of a device. One system uses a map network stored in a database to calculate current vehicle positions. These systems send distance and heading information, derived from either GPS or dead reckoning, to perform map matching. In other versions Light Detection and Ranging (LiDAR) data and Simultaneous Localization and Mapping (SLAM) are used to identify features surrounding an object using lasers or optics. Map matching calculates the current position based, in one instance, on the network of characteristics stored in a database. Other maps can also be used such as topographical maps that provide terrain characteristics or maps that provide a schematic and the interior layout of a building. These systems also use map matching to calibrate other sensors. Map matching, however, has inherent inaccuracies because map matching must look back in time and match historical data to observed characteristics of a position. As such, map matching can only calibrate the sensors or serve as a position determining means when a position is identified on the map. If a unique set of characteristics cannot be found that match the sensor's position in an existing database, the position derived from this method is ambiguous. Accordingly, on a long straight stretch of highway or in a region with minimal distinguishing geologic or structural features, sensor calibration or position determination using map matching may not occur for a significant period of time, if at all.
Dead reckoning is another means by which to determine the position of a device. Fundamentally, dead reckoning is based on knowing an object's starting position and its direction and distance of travel thereafter. Current land-based dead reckoning systems use an object's speed sensors, rate gyros, reverse gear hookups, and wheel sensors to “dead reckon” the object position from a previously known position. Dead reckoning is susceptible to sensor error and to cumulative errors from aggregation of inaccuracies inherent in time-distance-direction measurements. Furthermore, systems that use odometers and reverse gear hookups lack portability due to the required connections. Moreover, the systems are hard to install in different objects due to differing odometers' configurations and odometer data varies with temperature, load, weight, tire pressure and speed. Nonetheless, dead reckoning is substantially independent of environmental conditions and variations.
A known way of localizing a robot involves “trilateration”, which is a technique that determines position based on distance information from uniquely-identifiable ranging radios. Commonly, the robot also has a form of odometer estimation on board as well, in which case the ranges and odometer can be fused in a Kalman filter. However, over large periods of time the vehicle odometer cannot be trusted on its own. As such, what is really desired from the ranging radios is not a localization estimate, but a correction that can be applied to the odometer frame of reference to bring it inline with that of the actual robot's position. This transform should vary slowly over time, as such it can be assumed as a constant.
Current ranging-radio localization techniques will have a difficult time scaling to multiple vehicles or persons in the same area because of bandwidth limits. Current technology requires upwards of 40 Hz range updates from at least four ranging radios to give precise estimates of global frame motion. This alone is nearly at the update limit of the technology. Fewer required ranging radios (no trilateration) and significantly lower update rates will allow the technology to expand to environments with many more objects localized.
The most well know positioning system is the Global Navigation Satellite System (GNSS), comprised of the United States' Global Positioning System (GPS) and the Russian Federation's Global Orbiting Navigation Satellite System (GLONASS). A European Satellite System is on track to join the GNSS in the near future. In each case these global systems are comprised of constellations of satellites orbiting the earth. Each satellite transmits signals encoded with information that allows receivers on earth to measure the time of arrival of the received signals relative to an arbitrary point in time. This relative time-of-arrival measurement may then be converted to a “pseudo-range”. The position of a satellite receiver may be accurately estimated (to within 10 to 100 meters for most GNSS receivers) based on a sufficient number of pseudo-range measurements.
GPS/GNSS includes Naystar GPS and its successors, i.e., differential GPS (DGPS), Wide-Area Augmentation System (WAAS), or any other similar system. Naystar is a GPS system which uses space-based satellite radio navigation, and was developed by the U.S. Department of Defense. Naystar GPS consists of three major segments: space, control, and end-user segments. The space segment consists of a constellation of satellites placed in six orbital planes above the Earth's surface. Normally, constellation coverage provides a GPS user with a minimum of five satellites in view from any point on earth at any one time. The satellite broadcasts a RF signal, which is modulated by a precise ranging signal and a coarse acquisition code ranging signal to provide navigation data. This navigation data, which is computed and controlled by the GPS control segment for all GPS satellites, includes the satellite's time, clock correction and ephemeris parameters, almanac and health status. The user segment is a collection of GPS receivers and their support equipment, such as antennas and processors which allow users to receive the code and process information necessary to obtain position velocity and timing measurements.
Unfortunately, GPS may be unavailable in several situations where the GPS signals become weak, susceptible to multi-path interference, corrupted, or non-existent as a result of terrain or other obstructions. Such situations include urban canyons, indoor positions, underground positions, or areas where GPS signals are being jammed or subject to RF interference. Examples of operations in which a GPS signal is not accessible or substantially degraded include both civil and military applications, including, but not limited to: security, intelligence, emergency first-responder activities, and even the position of one's cellular phone.
In addition to GPS-type trilateration schemes another trilateration technique involves the use of radio frequency (RF) beacons. The position of a mobile node can be calculated using the known positions of multiple RF reference beacons (anchors) and measurements of the distances between the mobile node and the anchors. The anchor nodes can pinpoint the mobile node by geometrically forming four or more spheres surrounding the anchor nodes which intersect at a single point that is the position of the mobile node. Unfortunately, this technique has strict infrastructure requirements, requiring at least three anchor nodes for a 2D position and four anchor nodes for a 3D position. The technique is further complicated by being heavily dependent on relative node geometry and suffers from the same types of accuracy errors as GPS, due to RF propagation complexities.
Many sensor networks of this type are based on position measurements using such techniques which measure signal differences—differences in received signal strength (RSS), signal angle of arrival (AoA), signal time of arrival (ToA) or signal time difference of arrival (TDoA)—between nodes, including stationary anchor nodes. Ambiguities using trilateration can be eliminated by deploying a sufficient number of anchor nodes in a mobile sensor network, but this method incurs the increased infrastructure costs of having to deploy multiple anchor nodes.
Inertial navigation units (INUs), consisting of accelerometers, gyroscopes and magnetometers, may be employed to track an individual node's position and orientation over time. While essentially an extremely precise application of dead reckoning, highly accurate INUs are typically expensive, bulky, heavy, power-intensive, and may place limitations on node mobility. INUs with lower size, weight, power and cost are typically also much less accurate. Such systems using only inertial navigation unit (INU) measurements have a divergence problem due to the accumulation of “drift” error—that is, cumulative dead-reckoning error, as discussed above—while systems based on inter-node ranging for sensor positioning suffer from flip and rotation ambiguities.
Many navigation systems are hybrids which utilize a prescribed set of the aforementioned position-determining means to locate an object's position. The positioning-determining means may include GPS, dead reckoning systems, range-based determinations and map databases, but each is application-specific. Typically, one among these systems will serve as the primary navigation system while the remaining position-determining means are utilized to recalibrate cumulative errors in the primary system and fuse correction data to arrive at a more accurate position estimation. Each determining means has its own strengths and limitations, yet none identifies which of all available systems is optimized, at any particular instance, to determine the object's position.
The prior art also lacks the ability to identify which of the available positioning systems is unreliable or has failed and which among these systems is producing, at a given instant in time, the most accurate position of an object. Moreover, the prior art does not approach position estimation from a multimodal approach, but rather attempts to “fuse” collected data to arrive at a better—but nonetheless, unimodal—estimation. What is needed is an Adaptive Positioning System that can analyze data from each of a plurality of positioning systems and determine—on an iterative basis—which systems are providing the most accurate and reliable positional data, to provide a precise, multimodal estimation of position across a wide span of environmental conditions. Moreover, a need further exists to modify an object's behavior to accommodate the path- and speed-dependent accuracy requirements of certain positioning systems' position data. Additional advantages and novel features of this invention shall be set forth in part in the description that follows, and in part will become apparent to those skilled in the art upon examination of the following specification or may be learned by the practice of the invention. The advantages of the invention may be realized and attained by means of the instrumentalities, combinations, compositions, and methods particularly pointed out in the appended claims.